package org.czx.datactruct;

import java.util.Arrays;

/**
 * @author czx
 * @date 2020/9/21 14:07
 */
public class SortUtils {
    public static void main(String[] args) {
        int[] array = {16, 13, 2, 10, 11, 3, 6, 7, 8, 0, 5, 4, 15, 1, 14, 12, 9, 17, 18, 19};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 选择排序
     */
    public static void selectSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        //noOrderIndex 未排序的区域的起始下标
        for (int noOrderIndex = 0; noOrderIndex < array.length; noOrderIndex++) {
            int minIndex = getMinIndex(array, noOrderIndex);
            swap(array, noOrderIndex, minIndex);
        }
    }

    /**
     * 将数组中下标为i和j的两个元素位置交换
     * @param array
     * @param i
     * @param j
     */
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 获取数组中从start下标开始的最小元素的下标
     * @param array
     * @param start
     * @return
     */
    private static int getMinIndex(int[] array, int start) {
        int minIndex = start;  //最小元素的下标
        int min = array[minIndex];  //最小元素
        for (int curr = start + 1; curr < array.length; curr++) {
            //假如当前元素比已经记录的最小元素要小，就将最小元素的下标指向当前元素的下标
            if (array[curr] < min) {
                min = array[curr];
                minIndex = curr;
            }
        }
        return minIndex;
    }

    /**
     * 希尔排序
     */
    public static void shellSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        //gap 间隔，每次为原来的一半
        for (int gap = array.length / 2; gap > 0; gap = gap / 2) {
            for (int begin = 0; begin < gap; begin++) {
                //下面代码和插入排序类似，但它是和间隔gap个位置的元素比较
                for (int i = 0; i + gap < array.length; i += gap) {
                    for (int curr = i; curr > 0 && array[curr] < array[curr - gap]; curr -= gap) {
                        int temp = array[curr - gap];
                        array[curr - gap] = array[curr];
                        array[curr] = temp;
                    }
                }
            }
        }
    }

    /**
     * 插入排序
     *
     * @param array
     */
    public static void insertSort(int[] array) {
        //如果只有一个元素，不需要排序
        if (array == null || array.length < 2) {
            return;
        }
        for (int i = 1; i < array.length; i++) {
            //从第二个元素开始，与前面元素逐一比较，如果比前面的元素小，就插入那个位置
            // 由于前面的元素是排好序的，所以一旦发现当前的元素比前一个元素大，就可以停止迭代了
            for (int curr = i; curr > 0 && array[curr] < array[curr - 1]; curr--) {
                int temp = array[curr - 1];
                array[curr - 1] = array[curr];
                array[curr] = temp;
            }
        }
    }
}
